#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}

};

class Solution {
public:

   

    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0, n = nums.size() + 2;
        for (auto x : nums)  tmp ^= x;
        for (int i = 1; i <= n; i++)   tmp ^= i;

        int lowbit = tmp & (-tmp);

        int ret1 = 0, ret2 = 0;
        for (auto x : nums)
            if (x & lowbit)  ret1 ^= x;
            else    ret2 ^= x;
        for (int i = 1; i <= n; i++)
            if (i & lowbit)  ret1 ^= i;
            else    ret2 ^= i;
        return { ret1,ret2 };
    }

    string modifyString(string s) {
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '?')
                for (int tmp = 'a'; tmp <= 'z'; tmp++)
                {
                    if ((i == 0 || tmp != s[i - 1]) && (i == n - 1 || tmp != s[i + 1]))
                        s[i] = tmp;
                }
        }
        return s;
    }

    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int ret = 0, n = timeSeries.size();
        int i = 0;
        while (i < n)
        {
            int j = i + 1;
            int star = timeSeries[i];
            int end = timeSeries[i] +duration -1;
            while (j < n && end >= timeSeries[j])  end = timeSeries[j] + duration - 1, j++;
            ret += end - star+1;
            i = j;
        }
        return ret;
    }

    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ret;
        TreeNode* cur = root;
        ret.push_back(root->val);
        st.push(root);
        cur = cur->left;
        while (!st.empty() || cur != nullptr)
        {
            if (cur == nullptr)
            {
                cur = st.top()->right;
                st.pop();
            }
            else
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
        }
        return ret;
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) return ret;

        stack<TreeNode*> st;
        TreeNode* cur = root;
        st.push(cur);
        cur = cur->left;
        while (!st.empty() || cur)
        {
            if (cur && cur != st.top()->right)
            {
                st.push(cur);
                cur = cur->left;
            }
            else
            {
                cur = st.top()->right;
                if (cur == nullptr)
                {
                    ret.push_back(st.top()->val);
                    st.pop();
                    cur = st.top()->right;
                }
            }
        }
        return ret;
    }

    void _tree2str(TreeNode* root, string& s)
    {
        if (nullptr == root) return;

        char tmp[30] = { 0 };
        sprintf(tmp, "%d", root->val);
        s += tmp;

        if (root->left == nullptr)
        {
            if (root->right == nullptr)  return;
            else    s += "()";
        }
        else
        {
            s += "(";
            _tree2str(root->left, s);
            s += ")";
        }

        if (root->right == nullptr)  return;
        else
        {
            s += "(";
            _tree2str(root->right, s);
            s += ")";
        }
    }

    string tree2str(TreeNode* root) {
        string ret;
        _tree2str(root, ret);
        return ret;
    }

    class Solution {
    public:
        bool GetPath(TreeNode* root, TreeNode* n, stack<TreeNode*>& st)
        {
            if (root == nullptr)
                return false;

            st.push(root);

            if (root == n)
                return true;

            bool isPath = false;

            if (isPath = GetPath(root->left, n, st))
                return true;

            if (isPath = GetPath(root->right, n, st))
                return true;

            st.pop();
            return false;
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            stack<TreeNode*> pPath;
            stack<TreeNode*> qPath;

            GetPath(root, p, pPath);
            GetPath(root, q, qPath);

            TreeNode* ret = nullptr;

            int psize = pPath.size(), qsize = qPath.size();
            while (psize && qsize)
            {
                if (psize > qsize)
                {
                    pPath.pop();
                    psize--;
                }
                else if (psize < qsize)
                {
                    qPath.pop();
                    qsize--;
                }
                else
                {
                    if (pPath.top() == qPath.top())
                    {
                        ret = pPath.top();
                        break;
                    }
                    else
                    {
                        pPath.pop();
                        qPath.pop();
                        psize--;
                        qsize--;
                    }
                }
            }
            return ret;
        }
};

int main()
{
    Solution s;

    TreeNode n1(1);
    TreeNode n3(3);
    TreeNode n2(2);
    n1.right = &n2;
    n2.left = &n3;
    s.postorderTraversal(&n1);
    return 0;
}